/**
 *  一句话思路：
    算法描述：
    解决所需数据结构+算法：
**/
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

#define N 100010
#define M 500010

struct edge {
    int x, y, w, pre;
}e[M];
int elen = 0, last[N];

void ins(int x, int y, int w) {
    e[++elen] = {x, y, w, last[x]};
    last[x] = elen;
}

int d[N];
bool vis[N];
int n, m, s;

int main() {
    cin >> n >> m >> s;
    while(m--) {
        int u, v, w;
        cin >> u >> v >> w;
        ins(u, v, w);
    }

    memset(vis, false, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;

    for(int i=0; i<n; i++) {
        int x = 0;
        for(int j=1; j<=n; j++)
            if(!vis[j] && d[j] < d[x])
                x = j;
        vis[x] = true;
        for(int k=last[x]; k; k=e[k].pre) {
            int y = e[k].y;
            if(d[y] > d[x] + e[k].w)
                d[y] = d[x] + e[k].w;
        }
    }

    for(int i=1; i<=n; i++){
        if(d[i] == d[0])    cout << (1<<31)-1 << " ";
        else cout << d[i] << " ";
    }

    return 0;
}